package com.example.demo.leetcode.level2;

/**
 * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 *
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
 *
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 *
 * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
 *
 *  
 *
 */
public class 奇偶链表 {

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    public ListNode oddEvenList(ListNode head) {

            ListNode start = head,p=head,q=head,n = head;

            while(n.next != null){
                n = n.next;
            }

            boolean jishuFlag;
            if (head.val % 2 == 0){
                jishuFlag = false;
            }else{
                jishuFlag = true;
            }

            ListNode jishu = new ListNode();
            ListNode oushu = new ListNode();
            ListNode tempjishu = jishu;
            ListNode tempoushu = oushu;
            while((q = p) != null){
                if(p.val % 2 == 0){
                    p = p.next;
                    tempoushu.next = q;
                    tempoushu = tempoushu.next;
                    tempoushu.next = null;
                }else{
                    p = p.next;
                    tempjishu.next = q;
                    tempjishu = tempjishu.next;
                    tempjishu.next = null;
                }
            }

        if(jishuFlag){
            tempjishu.next = oushu.next;
            return jishu.next;
        }else{
            tempoushu.next = jishu.next;
            return oushu.next;
        }

    }


    public ListNode oddEvenList2(ListNode head) {

        if(head == null){
            return null;
        }
        ListNode start = head,p=head,q=head,n = head;

        while(n.next != null){
            n = n.next;
        }

        boolean jishuFlag;
        if (head.val % 2 == 0){
            jishuFlag = false;
        }else{
            jishuFlag = true;
        }

        ListNode jishu = new ListNode();
        ListNode oushu = new ListNode();
        ListNode tempjishu = jishu;
        ListNode tempoushu = oushu;
        int count=1;
        while((q = p) != null){
            if(count % 2 == 0){
                p = p.next;
                tempoushu.next = q;
                tempoushu = tempoushu.next;
                tempoushu.next = null;
            }else{
                p = p.next;
                tempjishu.next = q;
                tempjishu = tempjishu.next;
                tempjishu.next = null;
            }
            count++;
        }

            tempjishu.next = oushu.next;
            return jishu.next;

    }


}
